package com.leecode.xiehf.page_01;

import java.util.Arrays;

/**
 * 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 * <p>
 * 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 * <p>
 * 必须 原地 修改，只允许使用额外常数空间。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/next-permutation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0031 {

    public static void main(String[] args) {
        Solution_0031 solution_0031 = new Solution_0031();
        int[] nums = new int[]{1, 5, 1}; // 5 2 3 4 7
        solution_0031.nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 又是一个递归的逻辑
     */
    public void nextPermutation(int[] nums) {
        if (nums.length == 1) {
            return;
        }
        if (nums.length == 2) {
            int tmp = nums[0];
            nums[0] = nums[1];
            nums[1] = tmp;
            return;
        }
        int length = nums.length;
        int index = length - 1;
        while (index > 0) {
            if (nums[index] <= nums[index - 1]) {
                index--;
            } else {
                if (index == length - 1) {
                    int tmp = nums[index];
                    nums[index] = nums[index - 1];
                    nums[index - 1] = tmp;
                } else {
                    // 排序[index, length - 1]
                    int cur = length - 1;
                    while (nums[index - 1] >= nums[cur] && cur > index - 1) {
                        cur--;
                    }
                    int tmp = nums[cur];
                    nums[cur] = nums[index - 1];
                    nums[index - 1] = tmp;
                    sort(nums, index, length - 1);
                }
                return;
            }
        }
        if (index == 0) {
            // 倒序
            sort(nums, 0, length - 1);
        }
    }

    private void sort(int[] nums, int start, int end) {
        while (start < end) {
            // 交换左右的
            int tmp = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start++;
            end--;
        }
    }
}

